/*
剑指 Offer 66. 构建乘积数组
解题思路：表格法。需要一个新数组，初始化第一个值为1.第一次for循环根据公式res[i] = res[i - 1]*a[i - 1]，可得res数组为[1,1,2,6,24]
第二次for循环需要一个临时变量temp，根据公式 temp = temp * a[i + 1]可更新temp值，再更新res数组对应位置的结果。
 */
public class Offer66 {

  public static void main(String[] args) {
    int[] num = new int[]{1,2,3,4,5};
    int[] res = new Offer66().constructArr(num);
    for (int re : res) {
      System.out.println(re);
    }
  }

  public int[] constructArr(int[] a) {
    if (a.length == 0){
      return new int[0];
    }
    int res[] = new int[a.length];
    res[0] = 1;
    int temp = 1;
    for (int i = 1;i < a.length;++i){
      res[i] = res[i - 1]*a[i - 1];
    }
    for(int i = a.length - 2; i >= 0; i--) {
      temp = temp * a[i + 1];
      res[i] = res[i] * temp;
    }
    return res;
  }
}
